/**
 * 把一个数组最开始的若干元素搬到数组的末尾,我们称之为数组的旋转
 * 输入一个非递减排序的数组的一个旋转,输出旋转数组的最小元素
 * 例如数组:{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1
 * NOTE:给出的所有元素都大于0,若数组大小为0,请返回0
 */

/**
 * 采用二分查找的方式,进行定位
 * 1.定义首尾下标,因为是非递减数组旋转,所以旋转最后可以看成两部分,前半部分整体非递减
 *  后半部分整体非递减,前半部分整体大于后半部分
 * 2.假设: left指向最左侧,right指向最右侧,mid为二分之后的中间位置
 *  则:a[mid] >= a[left] 说明mid位置在原数组前半部分,进一步说明,目标最小值,在mid的右侧,让left=mid
 *  a[mid] < a[left],说明mid位置在原数组的后半部分,进一步说明,目标最小值,在mid的左侧,让right=mid
 *  这个过程会让[left,righ]区间变小
 *  此过程中,left永远在原数组的前半部分,right永远在原数组的后半部分
 *  当left和right相邻时,right指向的位置,就是最小的元素位置
 *
 */
public class suanfa02 {
    public int minNumberRotateArray (int[] array) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int left = 0;
        int right = array.length-1;
        int mid = 0;
        while (array[left] >= array[right]) {
            if (right - left == 1) {
                mid = right;
                break;
            }
            mid = left + ((right - left)>>1);
            if (array[left] == array[right] && array[mid] == array[left]) {//1
                int result = array[left];
                for (int i = left+1; i < right; i++) {//left和right值是相等的
                    if (array[i] < result) {
                        result = array[i];
                    }
                }
                return result;
            }
            if (array[mid] >= array[left]) {
                //说明mid 在原数组前半部分
                left = mid;
            }else {
                right = mid;
            }
        }
        return array[mid];
    }
}
